package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 朱城委 on 2021/11/24.<br><br>
 *
 * 中等：螺旋矩阵
 */
public class Topic54 {

    public static void main(String[] args) {
        Topic54 instance = new Topic54();
        int[][] array;

        array = new int[][] {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        System.out.println(instance.spiralOrder(array));

        array = new int[][] {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };
        System.out.println(instance.spiralOrder(array));
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int rows = matrix.length;
        int cols = matrix[0].length;
        int left = 0;
        int top = 0;
        int bottom = rows - 1;
        int right = cols - 1;

        while (left <= right && top <= bottom) {

            for(int col = left; col <= right; col++) {
                list.add(matrix[top][col]);
            }

            for(int row = top + 1; row <= bottom; row++) {
                list.add(matrix[row][right]);
            }

            if(left < right && top < bottom) {
                for(int col = right - 1; col > left; col--) {
                    list.add(matrix[bottom][col]);
                }

                for(int row = bottom; row > top; row--) {
                    list.add(matrix[row][left]);
                }
            }

            left++;
            top++;
            right--;
            bottom--;
        }

        return list;
    }

    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int rows = matrix.length;
        int cols = matrix[0].length;
        int size = rows * cols;

        int[][] visited = new int[rows][cols];
        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        int row = 0;
        int col = 0;
        for(int i = 0; i < size; i++) {
            list.add(matrix[row][col]);
            visited[row][col] = 1;

            int nextRow = row + direction[directionIndex][0];
            int nextCol = col + direction[directionIndex][1];
            if(nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols || visited[nextRow][nextCol] == 1) {
                directionIndex = (directionIndex + 1) % direction.length;
            }

            row += direction[directionIndex][0];
            col += direction[directionIndex][1];
        }

        return list;
    }
}
